import java.util.Stack;

/**
 * @Author ZhangCuirong
 * @Date 2025/9/19 8:17
 * @description:
 */
public class Solution678 {
    /**
     * 正反遍历时是可以的，若一个星号两次遍历分别可以让左括号和右括号使用，则该左括号和右括号可以为一对，此时星号为无效
     *
     * @param s
     * @return
     */
    public boolean checkValidString(String s) {
        int balance = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(' || c == '*') {
                balance++;
            } else if (c == ')') {
                balance--;
                if (balance < 0) {
                    return false;
                }
            }
        }
        balance = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            char c = s.charAt(i);
            if (c == ')' || c == '*') {
                balance++;
            } else if (c == '(') {
                balance--;
                if (balance < 0) {
                    return false;
                }
            }
        }
        return true;
    }

    /**
     * 如果字符串中没有星号，则只需要一个栈存储左括号，在从左到右遍历字符串的过程中检查括号是否匹配。
     * <p>
     * 在有星号的情况下，需要两个栈分别存储左括号和星号。从左到右遍历字符串，进行如下操作。
     * <p>
     * 如果遇到左括号，则将当前下标存入左括号栈。
     * <p>
     * 如果遇到星号，则将当前下标存入星号栈。
     * <p>
     * 如果遇到右括号，则需要有一个左括号或星号和右括号匹配，由于星号也可以看成右括号或者空字符串，因此当前的右括号应优先和左括号匹配，没有左括号时和星号匹配：
     * <p>
     * 如果左括号栈不为空，则从左括号栈弹出栈顶元素；
     * <p>
     * 如果左括号栈为空且星号栈不为空，则从星号栈弹出栈顶元素；
     * <p>
     * 如果左括号栈和星号栈都为空，则没有字符可以和当前的右括号匹配，返回 false。
     * <p>
     * 遍历结束之后，左括号栈和星号栈可能还有元素。为了将每个左括号匹配，需要将星号看成右括号，且每个左括号必须出现在其匹配的星号之前。当两个栈都不为空时，每次从左括号栈和星号栈分别弹出栈顶元素，对应左括号下标和星号下标，判断是否可以匹配，匹配的条件是左括号下标小于星号下标，如果左括号下标大于星号下标则返回 false。
     * <p>
     * 最终判断左括号栈是否为空。如果左括号栈为空，则左括号全部匹配完毕，剩下的星号都可以看成空字符串，此时 s 是有效的括号字符串，返回 true。如果左括号栈不为空，则还有左括号无法匹配，此时 s 不是有效的括号字符串，返回 false。
     *
     * @param s
     * @return
     */
    public boolean checkValidString2(String s) {
        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                stack1.push(i);
            } else if (c == '*') {
                stack2.push(i);
            } else if (c == ')') {
                if (!stack1.isEmpty()) {
                    stack1.pop();
                } else if (!stack2.isEmpty()) {
                    stack2.pop();
                } else {
                    return false;
                }
            }
        }
        while (!stack1.isEmpty() && !stack2.isEmpty()) {
            Integer a = stack1.pop();
            Integer b = stack2.pop();
            if (a >= b) {
                return false;
            }
        }
        if (!stack1.isEmpty()) {
            return false;
        }
        return true;
    }

    /**
     * 使用贪心的思想，可以将空间复杂度降到 O(1)。
     * <p>
     * 从左到右遍历字符串，遍历过程中，未匹配的左括号数量可能会出现如下变化：
     * <p>
     * 如果遇到左括号，则未匹配的左括号数量加 1；
     * <p>
     * 如果遇到右括号，则需要有一个左括号和右括号匹配，因此未匹配的左括号数量减 1；
     * <p>
     * 如果遇到星号，由于星号可以看成左括号、右括号或空字符串，因此未匹配的左括号数量可能加 1、减 1 或不变。
     * <p>
     * 基于上述结论，可以在遍历过程中维护未匹配的左括号数量可能的最小值和最大值，根据遍历到的字符更新最小值和最大值：
     * <p>
     * 如果遇到左括号，则将最小值和最大值分别加 1；
     * <p>
     * 如果遇到右括号，则将最小值和最大值分别减 1；
     * <p>
     * 如果遇到星号，则将最小值减 1，将最大值加 1。
     * <p>
     * 任何情况下，未匹配的左括号数量必须非负，因此当最大值变成负数时，说明没有左括号可以和右括号匹配，返回 false。
     * <p>
     * 当最小值为 0 时，不应将最小值继续减少，以确保最小值非负。
     * <p>
     * 遍历结束时，所有的左括号都应和右括号匹配，因此只有当最小值为 0 时，字符串 s 才是有效的括号字符串。
     *
     * @param s
     * @return
     */
    public boolean checkValidString3(String s) {
        int minCount = 0, maxCount = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                maxCount++;
                minCount++;
            } else if (c == '*') {
                minCount = Math.max(minCount - 1, 0);
                maxCount++;
            } else if (c == ')') {
                minCount = Math.max(minCount - 1, 0);
                maxCount--;
                if (maxCount < 0) {
                    return false;
                }
            }
        }
        return minCount == 0;
    }

    public static void main(String[] args) {
        Solution678 solution = new Solution678();
        System.out.println(solution.checkValidString("()"));
        System.out.println(solution.checkValidString("(*)"));
        System.out.println(solution.checkValidString("(*))"));
    }
}
